/*************************************************************************
	> File Name: 002.quick_union.java
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 四 10/ 7 00:22:04 2021
 ************************************************************************/

public class QuickUnionUF {
    private int[] id;

    public QuickUnionUF(int n) {
        id = new int[n];
        //set id of each object to itself (n array accesses)
        for (int i = 0; i < n; i++) id[i] = i;
    }

    private int root(int i) {
        //chase parent pointers until reach root (depth of i array accesses)
        while (i != id[i]) i = id[i];
        return i;
    }

    public boolean connected(int p, int q) {
        //check if p and q have same root (depth of p ans q array accesses)
        return root(p) == root(q);
    }

    public void union(int p, int q) {
        //change root of p to point to root of q (depth of p and q array accesses)
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }
}

